home *** CD-ROM | disk | FTP | other *** search
/ Graphics Plus / Graphics Plus.iso / msdos / raytrace / dbwrend / source / gifcompr.c < prev    next >
Text File  |  1989-11-04  |  9KB  |  353 lines
  1. /*
  2.  *
  3.  *  GIFENCOD.C  - GIF Image compression routines
  4.  *
  5.  *  Lempel-Ziv compression based on 'compress'.  
  6.  *  Original GIF modifications by David Rowley 
  7.  *   (mgardi@watdcsu.waterloo.edu)
  8.  *  Converted for use in RAYDSP by John Lowery.
  9.  *
  10.  */
  11.  
  12. #include <stdio.h>
  13. #include <stdlib.h>
  14. #include <io.h>
  15.  
  16. #include "display.h"
  17.  
  18. extern int ofil;         /* GIF output file handle */
  19.  
  20. /*
  21.  * General DEFINEs
  22.  */
  23.  
  24. #define CODEBITS     12
  25. #define HSIZE      5003            /* 80% occupancy */
  26.  
  27. /*
  28.  *
  29.  * GIF Image compression - modified 'compress'
  30.  *
  31.  * Based on: compress.c - File compression ala IEEE Computer, June 1984.
  32.  *
  33.  * By Authors:  Spencer W. Thomas       (decvax!harpo!utah-cs!utah-gr!thomas)
  34.  *              Jim McKie               (decvax!mcvax!jim)
  35.  *              Steve Davies            (decvax!vax135!petsd!peora!srd)
  36.  *              Ken Turkowski           (decvax!decwrl!turtlevax!ken)
  37.  *              James A. Woods          (decvax!ihnp4!ames!jaw)
  38.  *              Joe Orost               (decvax!vax135!petsd!joe)
  39.  *
  40.  */
  41.  
  42. static int n_bits;                      /* number of bits/code */
  43. static short maxcode;                   /* maximum code, given n_bits */
  44. static short maxmaxcode = 1<<CODEBITS;  /* should NEVER generate this code */
  45.  
  46. #define MAXCODE(n_bits)   (((short) 1 << (n_bits)) - 1)
  47.  
  48. static long htab[HSIZE];
  49. static unsigned short codetab[HSIZE];
  50.  
  51. #define HashTabOf(i)       htab[i]
  52. #define CodeTabOf(i)    codetab[i]
  53.  
  54. static short free_ent = 0;                  /* first unused entry */
  55.  
  56. /*
  57.  * block compression parameters -- after all codes are used up,
  58.  * and compression rate changes, start over.
  59.  */
  60.  
  61. static int  clear_flg = 0;
  62. static int  offset;
  63.  
  64. /*
  65.  * Algorithm:  use open addressing double hashing (no chaining) on the 
  66.  * prefix code / next character combination.  We do a variant of Knuth's
  67.  * algorithm D (vol. 3, sec. 6.4) along with G. Knott's relatively-prime
  68.  * secondary probe.  Here, the modular division first probe is gives way
  69.  * to a faster exclusive-or manipulation.  Also do block compression with
  70.  * an adaptive reset, whereby the code table is cleared when the compression
  71.  * ratio decreases, but after the table fills.  The variable-length output
  72.  * codes are re-sized at this point, and a special CLEAR code is generated
  73.  * for the decompressor.  Late addition:  construct the table according to
  74.  * file size for noticeable speed improvement on small files.  Please direct
  75.  * questions about this implementation to ames!jaw.
  76.  */
  77.  
  78. static int g_init_bits;
  79. static int ClearCode;
  80. static int EOFCode;
  81. static disk_error;
  82. static first_pass = TRUE;
  83. static short ent;
  84. static int hshift;
  85.  
  86.  
  87. static void output( short );
  88. static void cl_block( void );
  89. static void cl_hash( void );
  90. static void char_init( void );
  91. static void char_out( int );
  92. static void flush_char( void );
  93.  
  94. int gifPixel( c ) 
  95. short c;
  96. {
  97.      register short i;
  98.      register short disp;
  99.      register long  fcode;
  100.  
  101.  
  102.      if (first_pass)
  103.      {
  104.           disk_error = FALSE;
  105.  
  106.           /* Set up g_init_bits - initial number of bits */
  107.  
  108.           g_init_bits = BITS + 1;
  109.     
  110.           /*
  111.            * Set up the necessary values
  112.            */
  113.           offset = 0;
  114.           clear_flg = 0;
  115.           maxcode = MAXCODE(n_bits = g_init_bits);
  116.  
  117.           ClearCode = ( 1 << BITS );
  118.           EOFCode = ClearCode + 1;
  119.           free_ent = ClearCode + 2;
  120.     
  121.           char_init();
  122.         
  123.           ent = c;
  124.     
  125.           hshift = 0;
  126.           for ( fcode = HSIZE;  fcode < 65536L; fcode *= 2L )
  127.                hshift++;
  128.           hshift = 8 - hshift;      /* set hash code range bound */
  129.     
  130.           cl_hash();                /* clear hash table */
  131.     
  132.           /*
  133.            *   output the initial clear code
  134.            */
  135.           output( (short)ClearCode );
  136.           first_pass = FALSE;
  137.      }
  138.      else
  139.      {
  140.           
  141.           fcode = (long) (((long) c << CODEBITS) + ent);
  142.           i = (((short)c << hshift) ^ ent);    /* xor hashing */
  143.  
  144.           if ( HashTabOf (i) == fcode ) 
  145.           {
  146.                ent = CodeTabOf (i);
  147.                return(disk_error);
  148.           } 
  149.           else if ( (long)HashTabOf (i) < 0L )      /* empty slot */
  150.           {
  151.                goto nomatch;
  152.           }
  153.  
  154.           disp = HSIZE - i;           /* secondary hash (after G. Knott) */
  155.  
  156.           if ( i == 0 )
  157.                disp = 1;
  158.  
  159. probe:
  160.           if ( (i -= disp) < 0 )
  161.                i += HSIZE;
  162.  
  163.           if ( HashTabOf (i) == fcode ) 
  164.           {
  165.                ent = CodeTabOf (i);
  166.                return(disk_error);
  167.           }
  168.           if ( (long)HashTabOf (i) > 0L ) 
  169.                goto probe;
  170.  
  171. nomatch:
  172.           output ( (short) ent );
  173.           ent = c;
  174.           if ( free_ent < maxmaxcode ) 
  175.           {
  176.                CodeTabOf (i) = free_ent++; /* code -> hashtable */
  177.                HashTabOf (i) = fcode;
  178.           } 
  179.           else
  180.           {
  181.                cl_block();
  182.           }
  183.      }
  184.     return(disk_error);
  185. }
  186.  
  187. int gifFlush()
  188. {
  189.      output( (short) EOFCode );
  190.      return (disk_error);
  191. }
  192.  
  193. /*
  194.  * output()
  195.  *
  196.  * Output the given code.
  197.  * Inputs:
  198.  *      code:   A n_bits-bit integer.  If == -1, then EOF.  This assumes
  199.  *              that n_bits =< (long)wordsize - 1.
  200.  * Outputs:
  201.  *      Outputs code to the file.
  202.  * Assumptions:
  203.  *      Chars are 8 bits long.
  204.  * Algorithm:
  205.  *      Maintain a CODEBITS character long buffer (so that 8 codes will
  206.  * fit in it exactly).  When the buffer fills up empty it and start over.
  207.  */
  208.  
  209. static unsigned long cur_accum = 0;
  210. static int  cur_bits = 0;
  211.  
  212. static unsigned long masks[] = { 0x0000, 0x0001, 0x0003, 0x0007, 0x000F,
  213.                                          0x001F, 0x003F, 0x007F, 0x00FF,
  214.                                          0x01FF, 0x03FF, 0x07FF, 0x0FFF,
  215.                                          0x1FFF, 0x3FFF, 0x7FFF, 0xFFFF };
  216.  
  217. static void output( code )
  218. short  code;
  219. {
  220.      cur_accum &= masks[ cur_bits ];
  221.  
  222.      if( cur_bits > 0 )
  223.           cur_accum |= ((long)code << cur_bits);
  224.      else
  225.           cur_accum = code;
  226.  
  227.      cur_bits += n_bits;
  228.  
  229.      while( cur_bits >= 8 ) 
  230.      {
  231.           char_out( (unsigned int)(cur_accum & 0xff) );
  232.           cur_accum >>= 8;
  233.           cur_bits -= 8;
  234.      }
  235.  
  236.      /*
  237.       * If the next entry is going to be too big for the code size,
  238.       * then increase it, if possible.
  239.       */
  240.      if ( free_ent > maxcode || clear_flg ) 
  241.      {
  242.           if( clear_flg ) 
  243.           {
  244.                maxcode = MAXCODE (n_bits = g_init_bits);
  245.                clear_flg = 0;
  246.           } 
  247.           else 
  248.           {
  249.                n_bits++;
  250.                if ( n_bits == CODEBITS )
  251.                     maxcode = maxmaxcode;
  252.                else
  253.                     maxcode = MAXCODE(n_bits);
  254.           }
  255.      }
  256.     
  257.      if( code == EOFCode ) 
  258.      {
  259.           /*
  260.            * At EOF, write the rest of the buffer.
  261.            */
  262.  
  263.           while( cur_bits > 0 ) 
  264.           {
  265.                char_out( (unsigned int)(cur_accum & 0xff) );
  266.                cur_accum >>= 8;
  267.                cur_bits -= 8;
  268.           }
  269.           flush_char();
  270.  
  271.           if (disk_error)
  272.                writeError();
  273.      }
  274. }
  275.  
  276. /*
  277.  * Clear out the hash table
  278.  */
  279.  
  280. static void cl_block ()        /* table clear for block compress */
  281. {
  282.  
  283.      cl_hash();
  284.      free_ent = ClearCode + 2;
  285.      clear_flg = 1;
  286.  
  287.      output( (short)ClearCode );  /* tell the decoder what we're doing */
  288. }
  289.  
  290. static void cl_hash()          /* reset code table */
  291. {
  292.      memset( htab, (char) 0xFF, sizeof( htab));
  293. }
  294.  
  295.  
  296. /******************************************************************************
  297.  *
  298.  * GIF Specific routines
  299.  *
  300.  ******************************************************************************/
  301.  
  302. /*
  303.  * Number of characters so far in this 'packet'
  304.  */
  305.  
  306. static int a_count;
  307.  
  308. /*
  309.  * Set up the 'byte output' routine
  310.  */
  311. static void char_init()
  312. {
  313.      a_count = 0;
  314. }
  315.  
  316. /*
  317.  * Define the storage for the packet accumulator
  318.  */
  319.  
  320. static char accum[ 256 ];
  321.  
  322. /*
  323.  * Add a character to the end of the current packet, and if it is 254
  324.  * characters, flush the packet to disk.
  325.  */
  326. static void char_out( c )
  327. int c;
  328. {
  329.      accum[ a_count++ ] = c;
  330.      if( a_count >= 254 ) 
  331.           flush_char();
  332. }
  333.  
  334. /*
  335.  * Flush the packet to disk, and reset the accumulator
  336.  */
  337.  
  338. static void flush_char()
  339. {
  340.      if( a_count > 0 ) 
  341.      {
  342.           /* write the low byte only of a_count */
  343.           if ( write( ofil, (char *)&a_count, 1 ) != 1 ||
  344.                write( ofil, (char *)accum, a_count ) != a_count )
  345.           {
  346.                disk_error = TRUE;
  347.           }    
  348.           a_count = 0;
  349.      }
  350. }    
  351.  
  352. /* The End */
  353.